import javax.swing.tree.TreeNode;
import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2024-02-21
 * Time: 16:23
 */
public class TestBinaryTree {
    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    // 1、BM26 求二叉树的层序遍历(借助队列)
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        // write code here
        // 结果集
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        // 借助队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 先让根节点入队
        queue.offer(root);
        // 遍历队列：左右节点入队，遍历节点出队
        while (!queue.isEmpty()) {
            // 当前层结点数
            int size = queue.size();
            // 记录当前层的结果集
            ArrayList<Integer> tmp = new ArrayList<>();
            while (size != 0) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            res.add(tmp);
        }
        return res;
    }

    // 按照之字形打印（和层序遍历思想一致，只是加了个标志位）
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        if (pRoot == null) {
            return new ArrayList<>();
        }
        // write code here
        // 结果集
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        // 借助队列
        Deque<TreeNode> queue = new LinkedList<>();
        // 初始化根节点入队
        queue.offer(pRoot);
        // 为了打印之字形而设置的标志位flag:为true表示左->右；为false表示右->左
        boolean flag = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 每一层结果集
            ArrayList<Integer> tmp = new ArrayList<>();
            while (size != 0) {
                // 遍历节点出队，左右节点入队（如果有）
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size --;
            }
            if (!flag) {
                Collections.reverse(tmp);
            }
            res.add(tmp);
            flag = !flag;
        }
        return res;
    }

    // 求二叉树的最大深度（简单递归即可）
    public int maxDepth (TreeNode root) {
        // write code here
        // 思路：递归，返回左右子树的最大深度
        if (root == null) {
            return 0;
        }
        int leftDepth = 1 + maxDepth(root.left);
        int rightDepth = 1 + maxDepth(root.right);
        return leftDepth > rightDepth ? leftDepth : rightDepth;
    }

    // BM29 二叉树中和为某一值的路径(一)[从根节点到叶子结点，使用简单递归即可]
    public boolean hasPathSum (TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (sum == root.val && root.left == null && root.right == null) {
            return true;
        }
        // write code here
        return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
    }

    // BM30 二叉搜索树与双向链表（核心使用中序遍历，然后初始化两个结点-pre-head即可）
    // 初始化head返回头结点，即最小值结点，这里先初始化为null
    public TreeNode head = null;
    // 初始化pre前驱结点，初始为最小值，先初始化为null
    public TreeNode pre = null;

    public TreeNode Convert(TreeNode pRootOfTree) {
        // 核心：二叉搜索树中序遍历有序
        if (pRootOfTree == null) {
            return null;
        }
        // 左
        Convert(pRootOfTree.left);

        // 中
        if (head == null) {
            // 说明是第一个结点（最小值结点）
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
            // 非最小值结点
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }

        // 右
        Convert(pRootOfTree.right);
        // 这个返回值只有最后一次用得上
        return head;
    }

    // 对称的二叉树((这个重点看看，没想到))
    public boolean isSymmetrical (TreeNode pRoot) {
        // write code here
        if (pRoot == null) {
            return true;
        }
        return recursion(pRoot.left, pRoot.right);
    }
    private boolean recursion(TreeNode pRoot1, TreeNode pRoot2) {
        // 递归终止条件（终止及对称）
        if (pRoot1 == null && pRoot2 == null) {
            return true;
        }
        // 递归未终止说明不对称
        if (pRoot1 == null && pRoot2 != null) {
            return false;
        }
        if (pRoot1 != null && pRoot2 == null) {
            return false;
        }
        if (pRoot1 != null && pRoot2 != null && pRoot1.val != pRoot2.val) {
            return false;
        }
        return recursion(pRoot1.left, pRoot2.right) &&
                recursion(pRoot1.right, pRoot2.left);
    }

    // BM32 合并二叉树(这个也重点看看，没想到)
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        // write code here
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        // 都不为空的情况
        TreeNode node = new TreeNode(t1.val + t2.val);
        node.left = mergeTrees(t1.left,t2.left);
        node.right = mergeTrees(t1.right,t2.right);

        return node;
    }

    // BM33 二叉树的镜像(这个递归也好好看看，没写出来)
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if (pRoot == null) {
            return null;
        }
        // 递归左右子树
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);

        // 交换
        pRoot.left = right;
        pRoot.right = left;

        return pRoot;
    }


    // 判断是不是二叉搜索树（这个递归好好看看，思考思考）
    int pre2 = Integer.MIN_VALUE;
    public boolean isValidBST (TreeNode root) {
        // write code here
        if (root == null) {
            return true;
        }
        // 思路：中序遍历大于后续结点
        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.val < pre2) {
            return false;
        }
        pre2 = root.val;
        return isValidBST(root.right);
    }

    // 判断是否是完全二叉树（类似于层序遍历）
    public boolean isCompleteTree (TreeNode root) {
        // write code here
        // 和层序遍历类似，借助队列
        if (root == null) {
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        // 先将根节点入队
        queue.offer(root);
        //
        while (!queue.isEmpty()) {
            // 取出一个队列元素
            TreeNode node = queue.poll();
            if (node != null) {
                queue.offer(node.left);
                queue.offer(node.right);
            } else {
                // 对于完全二叉树来说是走到终点了
                // 对于非完全二叉树来说是遇到null了
                break;
            }
        }
        // 下面只需要遍历结果集，判断里面还有没有非空node即可
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                return false;
            }
        }
        return true;
    }

    // 判断是否是平衡二叉树
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here
        if (pRoot == null) {
            return true;
        }
        int leftHight = getDeep(pRoot.left);
        int rightHight = getDeep(pRoot.right);
        int res = Math.abs(leftHight - rightHight);
        if (res > 1) {
            return false;
        }
        return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
    }
    private int getDeep(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = 1 + getDeep(root.left);
        int right = 1 + getDeep(root.right);
        return left > right ? left : right;
    }

    // 找最近公共祖先（这个好好想想，我没整出来）
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //空树找不到公共祖先
        if(root == null)
            return -1;
        //pq在该节点两边说明这就是最近公共祖先
        if((p >= root.val && q <= root.val) || (p <= root.val && q >= root.val))
            return root.val;
            //pq都在该节点的左边
        else if(p <= root.val && q <= root.val)
            //进入左子树
            return lowestCommonAncestor(root.left, p, q);
            //pq都在该节点的右边
        else
            //进入右子树
            return lowestCommonAncestor(root.right, p, q);
    }

    // 普通二叉树找最近公共祖先，这个我写没写出来，好好看看
    public int lowestCommonAncestor2 (TreeNode root, int o1, int o2) {
        //没找到，返回-1
        if (root == null)
            return -1;
        //该节点是其中某一个节点
        if (root.val == o1 || root.val == o2)
            return root.val;
        //左子树寻找
        int left = lowestCommonAncestor2(root.left, o1, o2);
        //右子树寻找
        int right = lowestCommonAncestor2(root.right, o1, o2);
        //左子树为没找到，则在右子树中
        if (left == -1)
            return right;
        //右子树没找到，则在左子树中
        if (right == -1)
            return left;
        //否则是当前节点
        List<Integer> list = new ArrayList<>();
        return root.val;
    }

    // 建树函数1
    // （根据前序和中序重建二叉树）这个题很难，自己酌情看吧
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // write code here
        int n = preOrder.length;
        int m = vinOrder.length;
        //每个遍历都不能为0
        if (n == 0 || m == 0)
            return null;
        //构建根节点
        TreeNode root = new TreeNode(preOrder[0]);
        for (int i = 0; i < vinOrder.length; i++) {
            //找到中序遍历中的前序第一个元素
            if (preOrder[0] == vinOrder[i]) {
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(preOrder, 1, i + 1),
                        Arrays.copyOfRange(vinOrder, 0, i));
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(preOrder, i + 1, preOrder.length),
                        Arrays.copyOfRange(vinOrder, i + 1, vinOrder.length));
                break;
            }
        }

        return root;
    }

    //建树函数2
    //四个int参数分别是前序最左节点下标，前序最右节点下标
    //中序最左节点下标，中序最右节点坐标
    public TreeNode buildTree(int[] xianxu, int l1, int r1, int[] zhongxu, int l2, int r2){
        if(l1 > r1 || l2 > r2)
            return null;
        //构建节点
        TreeNode root = new TreeNode(xianxu[l1]);
        //用来保存根节点在中序遍历列表的下标
        int rootIndex = 0;
        //寻找根节点
        for(int i = l2; i <= r2; i++){
            if(zhongxu[i] == xianxu[l1]){
                rootIndex = i;
                break;
            }
        }
        //左子树大小
        int leftsize = rootIndex - l2;
        //右子树大小
        int rightsize = r2 - rootIndex;
        //递归构建左子树和右子树
        root.left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2 , l2 + leftsize - 1);
        root.right = buildTree(xianxu, r1 - rightsize + 1, r1, zhongxu, rootIndex + 1, r2);

        return root;
    }


    // BM39 序列化二叉树(前序序列化《==》前序反序列化)
    // 序列的下标
    public int index = 0;
    String Serialize(TreeNode root) {
        if (root == null) {
            return "#";
        }
        StringBuilder res = new StringBuilder();
        SerializeFunction(root,res);
        return res.toString();

    }
    private void SerializeFunction(TreeNode root,StringBuilder res) {
        if (root == null) {
            res.append("#");
            return;
        }
        // 根节点
        res.append(root.val).append(",");
        // 左子树
        SerializeFunction(root.left,res);
        // 右子树
        SerializeFunction(root.right,res);
    }
    TreeNode Deserialize(String str) {
        if (str == "#") {
            return null;
        }
        return DeserializeFunction(str);

    }
    private TreeNode DeserializeFunction(String str) {
        // 遇到空节点时
        if (str.charAt(index) == '#') {
            index ++;
            return null;
        }
        // 数字结点转换"10"表示两个字符
        int val = 0;
        while (str.charAt(index) != ',' && index != str.length()) {
            val = val * 10 + (str.charAt(index) - '0');
            index ++;
        }
        // 创建结点
        TreeNode node = new TreeNode(val);
        // 如果序列化到底了
        if (str.length() == index) {
            return node;
        } else {
            index ++;
        }
        // 递归构建左右子树
        node.left = DeserializeFunction(str);
        node.right = DeserializeFunction(str);
        return node;
    }

    // 根据二叉树创建字符串
    public String tree2str(TreeNode root) {
        // 这个返回值一定要利用起来！！！
        if (root == null) {
            return "";
        }
        if (root.left == null && root.right == null) {
            return new StringBuilder().append(root.val).toString();
        }
        if (root.right == null) {
            return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
        }
        return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")(")
                .append(tree2str(root.right)).append(")").toString();
    }

    // 判断是不是子树（结论：简单题一点都不简单）
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (subRoot == null) return true;   // t 为 null 一定都是 true
        if (root == null) return false;  // 这里 t 一定不为 null, 只要 s 为 null，肯定是 false

        if(isSameTree(root,subRoot)) {
            return true;
        }
        if(isSubtree(root.left,subRoot)) {
            return true;
        }
        if(isSubtree(root.right,subRoot)) {
            return true;
        }
        return false;

    }
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q!=null || p!=null && q==null) {
            return false;
        }
        //走到这里要么都是空 要么都不是空
        if(p==null && q==null) {
            return true;
        }
        if(p.val!=q.val) {
            return false;//不能return true
        }

        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    // 根据中后序列建树
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        TreeNode node = new TreeNode(postorder[postorder.length - 1]);
        int inorderIndex = 0;
        for (int i = inorder.length - 1; i >=0 ; i --) {
            if (inorder[i] == postorder[postorder.length-1]) {
                inorderIndex = i;
                break;
            }
        }
        node.left = buildTree(Arrays.copyOfRange(inorder, 0, inorderIndex),
                Arrays.copyOfRange(postorder, 0, inorderIndex));
        node.right = buildTree(Arrays.copyOfRange(inorder, inorderIndex+1, inorder.length),
                Arrays.copyOfRange(postorder, inorderIndex, postorder.length-1));
        return node;
    }

    public static void main(String[] args) {
        ThreadLocal<String> t = new ThreadLocal<>();

    }
}
